package 代码题.堆排序题目;

import java.util.HashMap;

/**
 * 一个无序数组，查找第k大的数
 */
public class Kmax {

    /**
     * 思路：使用堆排序，构造大顶堆。然后排序
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] arr = new int[]{1, 10, 2, 9, 3, 8, 4, 7, 5, 6};
        int k = 3;
        System.out.println(findKmax(arr, k));
    }

    private static int findKmax(int[] arr, int k) {
        //1.讲树结构进行小顶堆调整
        int len = arr.length / 2 - 1;
        for (int i = len; i >= 0; i--) {
            adjustheap(i, arr.length, arr);
        }

        for(int i=arr.length-1 ; i>arr.length-1-k; i--){
            //交换堆尾和根
            int tmp=arr[i];
            arr[i]=arr[0];
            arr[0]=tmp;

            adjustheap(0,i,arr);
        }
        return arr[arr.length-k];
    }

    //这是完全二叉树，不可能有单独的右节点
    private static void adjustheap(int i, int tail, int[] arr) {
        int temp = arr[i];
        //这里的本质是左右孩子的遍历
        for (int k = i * 2 + 1; k < tail; k = k * 2 + 1) {

            //左节点大于右节点,并且两个节点都没超出范围。这里决定两个节点的小值的位置
            if (k + 1 < tail && arr[k] < arr[k + 1]) {
                k++;
            }

            if (arr[k] > temp) {
                arr[i] = arr[k];
                i = k;
            } else {
                break;
            }
        }
        arr[i] = temp;
    }


}
